def CutRod(Prices, Length):

    Revs = [float('-inf')]*(len(Prices)+1)
    Revs[0] = 0

    for j in range(Length+1):

        q = float('-inf')

        for i in range(j+1):
            q = max(q, Prices[i] + Revs[j-i])

        Revs[j+1] = q

    return Revs[Length+1]

def cutRod(prices, rodLength):
    solution = [0]
    for j in range(rodLength):
        q = float('-inf')
        for i in range(0, j+1):
            q = max(q, prices[i] + solution[j - i])
        solution.append(q)
    return solution[-1]

if __name__ == '__main__':
    prices = [2, 3, 4, 0, 3, 5, 3, 2]
    length = 7
    print CutRod(prices, length)
